SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bitap algorithm</title>

</head>

Bitap algorithm

</h1>

</header>

The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an <a href="Approximate_string_matching" title="Approximate string matching">approximate string matching</a> algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of <a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a> – if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of <a href="Bitmask" class="mw-redirect" title="Bitmask">bitmasks</a> containing one bit for each element of the pattern. Then it is able to do most of the work with <a href="Bitwise_operation" title="Bitwise operation">bitwise operations</a>, which are extremely fast.

The bitap algorithm is perhaps best known as one of the underlying algorithms of the <a href="Unix" title="Unix">Unix</a> <a href="Programming_tool" title="Programming tool">utility</a> <a href="Agrep" title="Agrep">agrep</a>, written by <a href="Udi_Manber" title="Udi Manber">Udi Manber</a>, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general <a href="Regular_expression" title="Regular expression">regular expressions</a>.

Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the <a href="Word_length" class="mw-redirect" title="Word length">word length</a> of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length m, however, its <a href="Running_time" class="mw-redirect" title="Running time">running time</a> is completely predictable – it runs in <a href="Big_O_notation" title="Big O notation">O</a>(mn) operations, no matter the structure of the text or the pattern.

The bitap algorithm for exact string searching was invented by Bálint Dömölki in 1964<a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Domolki64">[1]</a><a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Domolki68">[2]</a> and extended by R. K. Shyamasundar in 1977<a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_shyamasundar77">[3]</a>, before being reinvented by <a href="Ricardo_Baeza-Yates" title="Ricardo Baeza-Yates">Ricardo Baeza-Yates</a> and <a href="Gaston_Gonnet" title="Gaston Gonnet">Gaston Gonnet</a><a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_BYG92">[4]</a> in 1989 (one chapter of first author's PhD thesis<a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_BY89">[5]</a>) which also extended it to handle classes of characters, wildcards, and mismatches. In 1991, it was extended by <a href="Udi_Manber" title="Udi Manber">Manber</a> and Wu <a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Manber91">[6]</a><a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Manber92">[7]</a> to handle also insertions and deletions (full fuzzy string searching). This algorithm was later improved by Baeza-Yates and <a href="Gonzalo_Navarro" title="Gonzalo Navarro">Navarro</a> in 1996.<a class="external autonumber external" href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_BN96">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Exact_searching">Exact searching</h2></div>

The bitap algorithm for exact <a href="String_searching_algorithm" class="mw-redirect" title="String searching algorithm">string searching</a>, in full generality, looks like this in pseudocode:

<pre>algorithm bitap_search is

input: text as a string.

pattern as a string.

output: string

m := length(pattern)

if m = 0 then

return text

/* Initialize the bit array R. */

R := new array[m+1] of bit, initially all 0

R[0] := 1

for i := 0; i < length(text); i += 1 do

/* Update the bit array. */

for k := m; k ≥ 1; k -= 1 do

R[k] := R[k - 1] & (text[i] = pattern[k - 1])

if R[m] then

return (text + i - m) + 1

return null

</pre>

Bitap distinguishes itself from other well-known string searching algorithms in its natural mapping onto simple bitwise operations, as in the following modification of the above program. Notice that in this implementation, counterintuitively, each bit with value zero indicates a match, and each bit with value 1 indicates a non-match. The same algorithm can be written with the intuitive semantics for 0 and 1, but in that case we must introduce another instruction into the <a href="Inner_loop" title="Inner loop">inner loop</a> to set <code>R |= 1</code>. In this implementation, we take advantage of the fact that left-shifting a value shifts in zeros on the right, which is precisely the behavior we need.

Notice also that we require <code>CHAR_MAX</code> additional bitmasks in order to convert the <code>(text[i] == pattern[k-1])</code> condition in the general implementation into bitwise operations. Therefore, the bitap algorithm performs better when applied to inputs over smaller alphabets.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> #include <string.h>

#include <limits.h>

const char *bitap_bitwise_search(const char *text, const char *pattern)

{

int m = strlen(pattern);

unsigned long R;

unsigned long pattern_mask[CHAR_MAX+1];

int i;

if (m == 0) return text;

if (m > 31) throw "The pattern is too long!";

/* Initialize the bit array R */

R = ~1;

/* Initialize the pattern bitmasks */

for (i=0; i <= CHAR_MAX; ++i)

pattern_mask[i] = ~0;

for (i=0; i < m; ++i)

pattern_mask[pattern[i]] &= ~(1UL << i);

for (i=0; text[i] != '\0'; ++i) {

/* Update the bit array */

R |= pattern_mask[text[i]];

R <<= 1;

if (0 == (R & (1UL << m)))

return (text + i - m) + 1;

}

return NULL;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Fuzzy_searching">Fuzzy searching</h2></div>

To perform fuzzy string searching using the bitap algorithm, it is necessary to extend the bit array R into a second dimension. Instead of having a single array R that changes over the length of the text, we now have k distinct arrays R1..k. Array Ri holds a representation of the prefixes of pattern that match any suffix of the current string with i or fewer errors. In this context, an "error" may be an insertion, deletion, or substitution; see <a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a> for more information on these operations.

The implementation below performs <a href="Probabilistic_record_linkage" class="mw-redirect" title="Probabilistic record linkage">fuzzy matching</a> (returning the first match with up to k errors) using the fuzzy bitap algorithm. However, it only pays attention to substitutions, not to insertions or deletions – in other words, a <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> of k. As before, the semantics of 0 and 1 are reversed from their conventional meanings.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> #include <stdlib.h>

#include <string.h>

#include <limits.h>

const char *bitap_fuzzy_bitwise_search(const char *text, const char *pattern, int k)

{

unsigned long *R;

int i, d;

if (pattern[0] == '\0') return text;

if (m > 31) return "The pattern is too long!";

/* Initialize the bit array R */

R = malloc((k+1) * sizeof *R);

for (i=0; i <= k; ++i)

R[i] = ~1;

/* Initialize the pattern bitmasks */

for (i=0; i < m; ++i)

for (i=0; text[i] != '\0'; ++i) {

/* Update the bit arrays */

unsigned long old_Rd1 = R[0];

R[0] |= pattern_mask[text[i]];

for (d=1; d <= k; ++d) {

unsigned long tmp = R[d];

/* Substitution is all we care about */

R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) << 1;

old_Rd1 = tmp;

}

if (0 == (R[k] & (1UL << m))) {

result = (text+i - m) + 1;

break;

}

free(R);

return result;

}

</pre></div>

<ul><li><a href="Agrep" title="Agrep">agrep</a></li>

<li><a href="TRE_(computing)" title="TRE (computing)">TRE (computing)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links_and_references">External links and references</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .citation{word-wrap:break-word}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}

/* end https://en.wikipedia.org/ */

</style><a href="#ref_Domolki64">^</a> Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.</li>

<li><a href="#ref_Domolki68">^</a> Bálint Dömölki, A universal compiler system based on production rules, <a href="BIT_Numerical_Mathematics" title="BIT Numerical Mathematics">BIT Numerical Mathematics</a>, 8(4), pp 262–275, 1968. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01933436">10.1007/BF01933436</a></li>

<li><a href="#ref_shyamasundar77">^</a> R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, <a href="International_Journal_of_Computer_Mathematics" title="International Journal of Computer Mathematics">International Journal of Computer Mathematics</a>, 6(2)pp 105–114, 1977.</li>

<li><a href="#ref_BY89">^</a> Ricardo Baeza-Yates. "Efficient Text Searching." PhD Thesis, University of Waterloo, Canada, May 1989.</li>

<li><a href="#ref_Manber91">^</a> Udi Manber, Sun Wu. "Fast text searching with errors." Technical Report TR-91-11. Department of Computer Science, <a href="University_of_Arizona" title="University of Arizona">University of Arizona</a>, Tucson, June 1991. (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20201017014251/ftp://ftp.cs.arizona.edu/agrep/agrep.ps.1.Z">gzipped PostScript</a>)</li>

<li><a href="#ref_BYG92">^</a> Ricardo Baeza-Yates, Gastón H. Gonnet. "A New Approach to Text Searching." <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>, 35(10): pp. 74–82, October 1992.</li>

<li><a href="#ref_Manber92">^</a> Udi Manber, Sun Wu. "Fast text search allowing errors." <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>, 35(10): pp. 83–91, October 1992, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F135239.135244">10.1145/135239.135244</a>.</li>

<li><a href="#ref_BN96">^</a> R. Baeza-Yates and G. Navarro. A faster algorithm for approximate string matching. In Dan Hirchsberg and Gene Myers, editors, Combinatorial Pattern Matching (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996.</li>

<li><a href="#ref_M99">^</a> G. Myers. "A fast bit-vector algorithm for approximate string matching based on dynamic programming." <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a> 46 (3), May 1999, 395–415.</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20120122013152/http://www.cod5.ch/archive/l/libbitap.html">libbitap</a>, a free implementation that shows how the algorithm can easily be extended for most regular expressions. Unlike the code above, it places no limit on the pattern length.</li>

<li>Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern Information Retrieval. 1999. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-39829-X</bdi>.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/polovik/Algorithms/blob/master/bitap.py">bitap.py</a> - Python implementation of Bitap algorithm with Wu-Manber modifications.</li></ol>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Strings176" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Strings176" style="font-size:114%;margin:0 4em"><a href="String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li>

<li><a href="Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li>

<li><a href="Edit_distance" title="Edit distance">Edit distance</a></li>

<li><a href="Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li>

<li><a href="Hamming_distance" title="Hamming distance">Hamming distance</a></li>

<li><a href="Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li>

<li><a href="Lee_distance" title="Lee distance">Lee distance</a></li>

<li><a href="Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li>

<li><a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>

<li><a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li>

<li><a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li>

<li><a href="Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li>

<li><a href="Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li>

<li><a href="Trigram_search" title="Trigram search">Trigram search</a></li>

<li><a href="Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li>

<li><a href="Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li>

<li><a href="Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular grammar</a></li>

<li><a href="Thompson's_construction" title="Thompson's construction">Thompson's construction</a></li>

<li><a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li>

<li><a href="Hirschberg's_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li>

<li><a href="Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li>

<li><a href="Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li>

<li><a href="Substring_index" title="Substring index">Substring index</a>

<ul><li><a href="Suffix_array" title="Suffix array">Suffix array</a></li>

<li><a href="Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix tree</a></li>

<li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="LCP_array" title="LCP array">LCP array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parsing" title="Parsing">Parsing</a></li>

<li><a href="Pattern_matching" title="Pattern matching">Pattern matching</a></li>

<li><a href="Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li>

<li><a href="Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li>

<li><a href="Longest_common_substring" title="Longest common substring">Longest common substring</a></li>

<li><a href="Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li>

<li>Sorting</li>

<li><a href="Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li>

<li><a href="String_operations" title="String operations">String operations</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-25" href="https://en.wikipedia.org/wiki/?title=Bitap_algorithm&oldid=1271757439">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>